Час 15 - Основни алгоритми - сабирање, бројање, множење, минимум, максимум¶
У наставку ћемо научити неколико основних алгоритама. Већину њих Python већ подржава у облику уграђених функција (које смо већ раније разматрали) и њих је заправо најчешће боље користити него их изнова програмирати. Са друге стране, учењем ових основних алгоритама учимо се процесу програмирања и учимо се да размишљамо алгоритамски. Иако смо целу ову област обележили као мало напреднију, ако кренеш да је истражујеш, приметићеш да постоје алгоритми за које смо сигурни да ћеш веома једноставно да их разумеш и научиш.
Сабирање¶
Обим многоугла¶
Напиши програм у коме се прво уноси број страница многоугла, затим се уносе дужине једне по једне странице и на крају се исписује обим тог многоугла.
Циљ овог задатка је да нас уведе у различите технике израчунавања збира неколико бројева. Да бисмо једноставније разумели технику која се користи за израчунавање збира бројева, олакшајмо мало задатак тако што ћемо уместо обима многоугла израчунавати обим троугла. Директан начин да се то уради је следећи:
Прво смо учитали сва три броја (зато су нам биле потребне три променљиве) и тек онда смо израчунали обим. Овај начин није директно применљив на случај многоугла јер не знамо колико ће нам променљивих бити потребно (чак иако знамо, њих може бити пуно и такав програм би био непотребно дугачак).
Други начин израчунавања обима троугла ће бити такав да ћемо мењати вредност збира након сваког учитавања дужине странице. У првом кораку поставићемо вредност збира (обима) на прву учитану вредност, а у сваком следећем кораку увећаваћемо текућу вредност збира за вредност учитану у том кораку (подсетимо се, вредности променљивих се могу мењати током извршавања програма).
Ако извршимо претходни програм корак-по-корак, можемо приметити да у
првом кораку променљива obim има вредност дужине прве странице, у
другом збира дужина прве и друге странице, а да у трећем збира дужина
све три странице.
Приметимо да су други и трећи корак једнаки и могу се извршити у петљи.
Програм додатно можемо поједноставити ако и први корак сведемо на облик у којем су друга два и њега убацимо у петљу. Зато приметимо да важи да је \(a + b + c = ((0 + a) + b) + c\) (нула је сабирак који не утиче на вредност збира - каже се да је нула неутрални елемент приликом сабирања). Збир се, дакле, може на почетку поставити (кажемо иницијализовати) на нулу, и затим се на њега може додавати један по један сабирак. Кажемо са се у сваком кораку збир ажурира.
Претходни програм се може једноставније реализовати уз помоћ петље:
Напокон, овај програм можемо веома једноставно уопштити тако да ради и за многоуглове.
Каже се да је овај програм заснован на шаблону који се некада називa акумулатор, редукција или fold и видећемо га у разним алгоритмима који следе. Заснива се на томе да се променљива која треба да садржи коначан резултат иницијализује на неку вредност, а затим да се у сваком кораку петље ажурира и нова вредност јој се израчуна на основу њене тренутне вредности и тренутног елемента серије која се обрађује. У нашем примеру променљива која израчунава збир се иницијализује на нулу, а у сваком кораку нова вредност јој се израчунава тако што се на претходну вредност збира дода нови сабирак. Приметимо да и пре петље и током извршавања петље и након петље променљива садржи тачно збир свих до тада учитаних елемената серије тј. свих до тада учитаних дужина странице многоугла.
Укупан рачун¶
Ако је позната листа цена производа у корпи израчуна укупан рачун.
Овај задатак смо већ разматрали када смо причали о уграђеним
функцијама за рад са листама, међу којима се налазила и функција
sum која служи за израчунавање збира елемената листе.
Међутим, на овом месту желимо да прикажемо да се збир може израчунати и применом алгоритма сабирања. Модификуј наредни програм тако да исправно израчуна укупну цену.
Укупан број лоптица испред Карела¶
Карел се налази испред пуно лоптица и жели да израчуна њихов укупан
број. Сваки пут када се робот покрене, испред њега се лоптице
распореде другачије. На сваком пољу је написан број лоптица на
њему. Када је Карел на том пољу он број лоптица може сазнати
позивом функције broj_loptica_na_polju(). Карел тренутно само изговара
број лоптица на сваком пољу. Поправи програм тако да се исправно
израчунава укупан број лоптица.
(карел_сабира)
Да резимирамо, збир серије бројева се може израчунати тако што се променљива иницијализује на нулу, а затим јој се додаје један по један елемент серије.
Бројање¶
Број елемената у листи¶
Напиши програм који израчунава број елемената листе.
Ко је добро научио лекцију о листама вероватно се сећа да се дужина
листе може (и треба) израчунати помоћу уграђене функције
len. Међутим, кроз овај задатак желимо да прикажемо алгоритам
бројања. На почетку петље бројач елемената иницијализоваћемо на нулу,
а онда ћемо у сваком кораку петље која пролази кроз елементе листе
бројач увећавати за један.
Приметимо сличност са алгоритмом сабирања (једина разлика је то што се уместо увећавања збира за вредност текућег елемента бројач увећава за један).
Број унетих имена¶
Напиши програм који уноси имена ученика све док се не унесе празна ниска и на крају пријављује колико имена је унето.
Пробај да допуниш наредни програм тако да коректно броји унета имена.
Број корака до зида¶
Карел се налази на почетку лавиринта и занима га колико је корака потребно да направи да би стигао до зида. Напиши програм који му у томе помаже.
Сваки пут када се помери напред, Карел треба да увећа бројач за један.
(карел_broji)
Просечна температура¶
Напиши програм који израчунава просечну температуру ако је дата листа која садржи температуре сваког дана током неког периода.
Подсетимо се просечна вредност елемената листе може одредити тако што
се збир свих елемената листе подели бројем елемената те
листе. Најлакши и најбољи начин да се то уради је да се употребе
уграђене функције sum и len.
Међутим, вежбе ради, хајде да урадимо овај задатак без примене уграђених функција, комбиновањем алгоритама сабирања и бројања. Приметимо да можемо у једној петљи проћи кроз елементе листе и истовремено рачунати и збир и број елемената листе.
Множење¶
Запремина квадра¶
Напиши програм који израчунава запремину квадра чије се дужине страница уносе (запремина квадра једнака је производу дужина његове три странице).
Овај задатак је веома сличан оном у којем се израчунавао обим троугла, једино што се уместо збира три броја захтева израчунавање производа три броја. Директно решење је зато веома слично:
И у овом случају желимо да стигнемо до решења у којем се бројеви учитавају и обрађују у петљи, како бисмо касније могли да га уопштимо и применимо на проблем проналажења производа више бројева. Производ се може поступно израчунавати тако што се помноже прво прва два броја, па се затим добијени производ помножи трећим бројем. Заиста, важи да је \(а \cdot b \cdot c = (a \cdot b) \cdot c\). Међутим, и у овом случају желимо да сва три броја обрађујемо на исти начин. Ако бисмо производ иницијализовали на нулу, он би до краја остао једнак нули јер важи да је \(((0 \cdot a) \cdot b) \cdot c = 0\). Међутим, ако производ иницијализујемо на један, добијамо тачно оно што нам треба (јер важи да је \(а \cdot b \cdot c = ((1 \cdot a) \cdot b) \cdot c\)). Као што је нула био број који не утиче на сабирање (који је неутрални елемент за сабирање), тако је један број који не утиче на множење (он је неутрални елемент за множење). Дакле, програм за израчунавање запремине, тј. производа три унета броја се може дефинисати на следећи начин.
Пошто се исте наредбе понављају три пута, још је боље решење да се употреби петља.
Дакле, производ можемо израчунати тако што се његова вредност у почетку иницијализује на 1, а затим ажурира тако што се у сваком кораку множи текућом вредношћу.
Приметимо изузетну сличност алгоритма израчунавања збира и
алгоритма израчунавања производа. Једина разлика је то што се у
иницијализацији збир иницијализује на нулу, а производ на јединицу
и то што се током ажурирања збира користи сабирање тј. оператор
+, а током ажурирања производа користи множење тј. оператор
*. Приметимо да и овај алгоритам користи шаблон акумулатор.
Степеновање¶
Када је \(n\) природан број, производ бројева \(n \cdot x\) означава збир који садржи \(n\) сабирака \(x\) тј. збир \(\underbrace{x + \ldots + x}_n\). Слично се може посматрати производ који садржи \(n\) чинилаца \(x\) тј. производ \(\underbrace{x \cdot \ldots \cdot x}_n\). У математици се такав производ назива степен и обележава се са \(x^n\). Тако је, на пример, \(2^4 = 2 \cdot 2 \cdot 2 \cdot 2 = 16\). Дефиниши функцију која за дате параметре \(x\) и \(n\) израчунава \(x^n\).
Рецимо да Python подржава директно операцију степеновања и она се
изражава оператором ** и тражени степен се може једноставно
изразити помоћу x ** n. Ипак, вежбе ради, желимо да степен
дефинишемо применом алгоритма множења.
Пшеница на шаховској табли¶
Легенда каже да је изумитељ игре шах од свог владара тражио да га награди тако што ће на прво поље шаховске табле ставити једно зрно пшенице, на друго два зрна, на треће четири и тако даље, стављајући на свако поље дупло више зрна пшенице него на претходно. Владар се насмејао како је малу награду изумитељ тражио, међутим, када је кренуо да броји зрна, брзо је схватио да у целом краљевству нема довољно пшенице да би исплатио награду. Напиши програм који исписује колико на сваком од поља има зрна пшенице, као и колико је укупно пшенице на целој табли.
Током рада програма одржаваћемо променљиву која чува број зрна на тренутном пољу (њена вредност креће од 1 и у сваком кораку се увећава за 2) и укупан број зрна на пољима до тог (њена вредност креће од 0 и у сваком кораку се увећава за број зрна на текућем пољу). Тело петље у којем се исписује број зрна на текућем пољу и у којој се ажурирају вредности променљивих (израчунава се њихова нова вредност) поновићемо 64 пута.
Обавезно изврши овај програм корак по корак и посматрај како се у сваком кораку петље мењају вредности променљивих.
Факторијел¶
Напиши пограм који израчунава на колико начина се \(n\) деце може распоредити на \(n\) столица.
Једно дете може на једну столицу сести само на један начин. Двоје деце може на две столице сести на два начина: прво дете на прву столицу, друго на другу или друго дете на прву столицу, а прво на другу. Обележимо ове начине са 12 и 21. Три детета могу сести на три столице на шест начина: 123, 132, 213, 231, 312, 321. На пример, распоред 231 означава да друго дете седи на првој столици, треће на другој, а прво дете на првој столици. Размотримо како у општем случају можемо израчунати број начина. На прву столицу може да седне било које од \(n\) деце. Након тога остаје \(n-1\) дете и исто толико столица, па на другу столицу може стати било које од те деце. На трећу столицу може сести било које од преостала \(n-2\) детета и тако даље, све док на последњу столицу не седне последње преостало дете. Зато је број начина једнак је производу бројева \(n\), \(n-1\), \(n-2\) итд. све до \(1\), тј. производу \(n\cdot(n-1)\cdot(n-2)\cdot \ldots 2\cdot 1\). Тај производ се у математици често јавља, па има посебно име и ознаку - обележава се са \(n!\), а назива факторијел броја \(n\).
Дакле, овај број можемо решити тако што израчунамо производ свих бројева од \(1\) до \(n\).
Минимум, максимум¶
Размотримо сада проблем одређивања највећег или најмањег елемената
између неколико датих бројева. Један начин да се то уради је коришћење
уграђене функције min тј. max за одређивање минимума
тј. максимума листе бројева.
Највиши од четири другара¶
Ако су познате висине четири другара, одреди висину највишег од њих.
Решење засновано на листама и функцији за рачунање максимума листе смо већ раније видели.
У наставкућемо видети како да ово постигнемо и без листа и уграђених
функција. Функција max се може применити на листу, међутим, могуће
је применити и на више бројева. Тако смо задатак могли решити и без
коришћења листе.
Често програмски језици нуде само функцију за одређивање већег тј. мањег од два задата броја (није јој могуће навести више од два аргумента). Максимум више бројева се може свести на узастопну примену ове функције.
Приметимо да смо и збир више бројева рачунали тако што смо узастопно
примењивали операцију сабирања два броја. Тако је збир a + b + c +
d рачунат као ((a + b) + c) + d, тј. као zbir(zbir(zbir(a, b),
c), d). Ово нам указује на то да и максимум више бројева можемо
израчунати на сличан начин на који смо рачунали збир - максимум
иницијализујемо на први елемент и онда га у сваком наредном кораку
ажурирамо на већу вредност од досадашњег максимума и текућег елемента.
Изврши претходни програм корак по корак, и прати како се мења вредност
променљиве najvisi.
Ако се елементи налазе у листи или се учитавају са улаза, онда можемо да употребимо и петље.
Програм можемо да уопштимо и на већи број особа.
У оба случаја први елемент је обрађиван пре петље, различито од свих
осталих. У програму у којем смо рачунали збир и производ, видели смо
да све елементе можемо да обрађујемо на исти начин ако за почетну
вредност узмемо 0, тј. 1, јер су то вредности које не утичу на збир
(рекли смо да се такве вредности називају неутралним). Наиме, важи да
је \(a + b + c = ((0 + a) + b) + c\) тј. да је zbir(zbir(a, b),
c) исто што и zbir(zbir(zbir(0, a), b), c), зато што за било
који број a важи да је zbir(a, 0) једнак a. Питање је да
ли нешто слично можемо да урадимо и за минимум тј. максимум. Потребно
је да пронађемо вредност x тако да за било који број a важи да
је max(x, a) = a, тј. број који је мањи или једнак било ком другом
броју. То је у општем случају број минус бесконачно \(-\infty\),
међутим, њега не умемо да запишемо у програму. Ако знамо да међу
бројевима чији ћемо максимум рачунати неће бити бити негативних, онда
за почетну вредност можемо узети нулу јер у том случају важи да је
max(max(a, b), c) = max(max(max(0, a), b), c).
Слично, ако знамо да ће сви бројеви чији максимум рачунамо бити већи
или једнаки неком броју x за почетну вредност можемо узети тај
број (или било који број мањи од њега).
Када рачунамо минимум, за почетну вредност треба да узмемо вредност
која је већа или једнака било ком другом броју, а то је вредност плус
бесконачно \(+\infty\). Ако знамо да су сви бројеви чији минимум
рачунамо мањи или једнаки неком броју x за почетну вредност можемо
узети тај број (или било који број већи од њега).
Проналажење максимума тј. минимума може се реализовати и без употребе
функције max тј. min. Функцију која рачуна већи од два броја
можемо једноставно реализовати коришћењем гранања.
Ако то узмемо у обзир тада najvisi = max(visina, najvisi) можемо
заменити следећом наредбом гранања.
Лако се примећује да je наредба гранања сувишна (јер не производи никакав видљив ефекат).
Тако се највећа висина може наћи на следећи начин, без употребе
функције max (пошто знамо да су све висине позитивне, максимум
иницијализујемо на нулу).
Слично можемо израчунати и најмању висину (минимум ћемо иницијализовати на први елемент листе).
Тражење максимума три или четири броја се може засновати и на испитивању свих могућих односа тих бројева. На пример,
Као што видите, сва ова решења су веома ружна и стога их треба избегавати.
Највећи број лоптица испред Карела¶
Карел се налази испред поља са лоптицама и жели да сазна колики је
највећи број лоптица на неком од поља испред њега. Број лоптица на
пољу на којем се налази Карел може сазнати позивом функције
broj_loptica_na_polju(). Карел тренутно само изговара број
лоптица на сваком пољу. Поправи програм тако да се исправно
израчунава највећи број лоптица.
(карел_тражи_максимум)
Џепарац¶
Некада нас не занима вредност максимума тј. минимума, већ позиција на којој се тај максимум тј. минимум налази. Да бисмо то израчунали, потребно је да уз текућу вредност максимума тј. минимума памтимо и текућу вредност његове позиције.
Радица је добијала џепарац током пет дана у недељи. Ког дана је добила највећи џепарац (ако је то понедељак онда испиши 1, ако је то уторак онда 2 и тако даље).
Лепше решење се може добити ако се употреби петља:
Пошто су сви износи позитивни, максимум се може иницијализовати на нулу. Прилагоди програм тако да коректно одреди тражене податке.
Ако се тражи позиција максималне вредности у листи, тада је довољно памтити само позицију текућег максимума, пошто се текућа вредност максимума може прочитати из листе када се позиција зна. Потребно је само обратити пажњу на то да се индекси (позиције елемената) у листи броје од нуле.